/*
 * @lc app=leetcode.cn id=767 lang=javascript
 *
 * [767] 重构字符串
 */

// @lc code=start
/**
 * @param {string} S
 * @return {string}
 */
var reorganizeString = function (S) {
  const size = S.length;
  const idxs = new Array(26).fill(0);
  for (let i = 0; i < size; i++) {
    let key = S[i].charCodeAt() - 97;
    idxs[key]++;
  }

  let maxCount = 0;
  maxCount = Math.max(...idxs);
  if (maxCount > Math.floor((size + 1) / 2)) {
    return '';
  }

  let evenIdx = 0;
  let oddIdx = 1;
  const result = new Array(size);
  idxs.forEach((_, index) => {
    const char = String.fromCharCode(index + 97);
    while (
      idxs[index] > 0 &&
      oddIdx < size &&
      idxs[index] <= Math.floor(size / 2)
    ) {
      result[oddIdx] = char;
      oddIdx += 2;
      idxs[index]--;
    }
    // 最多数量的字符串需要放在偶数位置
    while (idxs[index] > 0) {
      result[evenIdx] = char;
      evenIdx += 2;
      idxs[index]--;
    }
  });

  return result.join('');
};
// @lc code=end
